#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <stack>
using namespace std;

struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};

class Solution {
public:
	TreeNode* Convert(TreeNode* pRootOfTree) {
		if (!pRootOfTree)
			return pRootOfTree;
		stack<TreeNode*> st;
		TreeNode* pre = nullptr;
		TreeNode* cur = pRootOfTree;
		TreeNode* head = nullptr;
		int flag = 1;
		while (cur || !st.empty())
		{
			while (cur)
			{
				st.push(cur);
				cur = cur->left;
			}
			cur = st.top();
			st.pop();
			if (flag == 1)
			{
				flag = 0;
				head = cur;
				pre = head;
			}
			else {
				pre->right = cur;
				cur->left = pre;
				pre = cur;
			}
			cur = cur->right;
		}
		return head;
	}
};

int main()
{
	return 0;
}
